//================v2要点总结===============
/**
 * 1.找规律，二叉树，每一层最小值等于层数 L，最大值等于2L
 * 2.下一层数字num,如果分别为最小最大值，则个数为1，否则为上一层 count(num - 1) + count(num - 2)
 *
 */

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n <= 2) {
    return n;
  }

  let level = 2;
  let rslt = 0;
  let arr = new Array(n + 1).fill(0);
  arr[1] = 1;
  arr[2] = 1;
  for (let i = 0; i < n; i++) {
    // 采用倒写的方式，避免改动依赖的值
    for (let col = 2 * level - 1; col > level; col--) {
      arr[col] = arr[col - 1] + arr[col - 2];
    }
    arr[level] = 1;
    arr[2 * level] = 1;
    if (n >= level && n <= 2 * level) {
      rslt += arr[n];
    }

    level++;
  }
  arr = null;
  return rslt;
};

console.log(climbStairs(44));
